<?php

/**
 * 顺序查找,时间复杂度O(n)
 * @param $sk
 * @param $arr
 */
function SequenceSearch($sk, $arr) {
    for ($i = 0; $i < count($arr); $i++) {
        if ($sk == $arr[$i]) {
            echo "查到了index是:" . $i . ", ";
            break;
        }
    }
    echo "线性查找次数: " . $i, PHP_EOL;
}

/**
 * 二分查找,必须是有序的数组,时间复杂度O(logN)
 * @param $sk
 * @param $arr
 */
function BinarySearch($sk, $arr) {
    $left = 0;
    $right = count($arr) - 1;
    $i = 0;
    while ($left <= $right) {
        $i++;
        $mid = (int)(($left + $right) / 2);
        if ($arr[$mid] > $sk) {
            $right = $mid - 1;
        } else if ($arr[$mid] < $sk) {
            $left = $mid + 1;
        } else {
            echo "查到了index是:" . $mid . ", ";
            break;
        }
    }
    echo "二分查找次数: " . $i, PHP_EOL;
}

$arr = [5, 6, 19, 25, 4, 33, 56, 37, 91, 23];
$searchKey = 56;
SequenceSearch($searchKey, $arr); //查到了index是:6, 线性查找次数: 6

sort($arr); //先排序
print_r($arr); //[4,5,6,19,23,25,33,37,56,91]
BinarySearch($searchKey, $arr); //查到了index是:8, 二分查找次数: 3

//数据基数较大时,二分查找的效率会明显提升(对数级别, 2的17次方, 就能覆盖十万以内的数)
//在合适的情况下可以选用一个 O(logN) 的排序算法，这样总体的时间复杂度就还能保持在对数级别了
$arr = range(1, 100000);
$searchKey = 100000;
SequenceSearch($searchKey, $arr); //查到了index是:99999, 线性查找次数: 99999
BinarySearch($searchKey, $arr); //查到了index是:99999, 二分查找次数: 17
